Universidad de Costa Rica 04/Jun/2003
Escuela de Ciencias de la Computación e Informática I Semestre 2003
CI-1310 Sistemas Operativos Prof. Francisco Arroyo Mora
A) (15 puntos) Considere el siguiente conjunto de procesos, cada uno constituido por un único "cpu-burst".
|
Proceso |
Burst-Time (ms) |
Prioridad |
|
P1 |
2 + X2 |
X3 |
|
P2 |
5 + X2 |
X2 |
|
P3 |
1 + X3 |
X5 |
|
P4 |
4 + X4 |
X6 |
|
P5 |
3 + X6 |
X4 |
En donde X1X2X3X4X5X6 representa su número de carné. La prioridad más alta está dada por el número más bajo. Todos los procesos llegaron al mismo tiempo en el orden indicado por su subíndice.
a) (8 puntos) Haga una gráfica la ejecución de los procesos si se emplea FCFS, SJF, Round Robin (q = 5 ms) y Prioridades.
b) (7 puntos) Calcule el tiempo de espera y "throughput" (t=15 ms) para cada proceso en todos los algoritmos y el tiempo de espera promedio.
B) (10 puntos) Considere un sistema compuesto de m recursos del mismo tipo que son compartidos por n procesos. Los recursos pueden ser solicitados y devueltos solo uno a la vez. Pruebe que es un sistema libre de deadlock si las siguientes condiciones se dan: a) La necesidad máxima de cada proceso está entre 1 y m, b) La suma de las necesidades máximas de todos los procesos es menor que m + n.
C) (10 puntos) Suponga que las siguientes estructuras de datos están definidas para el algoritmo del banquero:
AVAILABLE |
A |
B |
C |
D |
|
||||||
|
|
1 |
5 |
2 |
0 |
|
||||||
|
|
|
||||||||||
Allocation |
Max |
||||||||||
|
|
A |
B |
C |
D |
A |
B |
C |
D |
|||
P0 |
0 |
0 |
1 |
2 |
0 |
0 |
1 |
2 |
|||
P1 |
1 |
0 |
0 |
0 |
1 |
7 |
5 |
0 |
|||
P2 |
1 |
3 |
5 |
4 |
2 |
3 |
5 |
6 |
|||
P3 |
0 |
6 |
3 |
2 |
0 |
6 |
5 |
2 |
|||
P4 |
0 |
0 |
1 |
4 |
0 |
6 |
5 |
6 |
|||
a) (5 puntos) Determine si el sistema está en un estado seguro.
b) (5 puntos) Si llega una solicitud de P1 para (0,4,2,0) se podrá asignar inmediatamente, o el proceso debe esperar?
D) (20 puntos) Sea un bar de dudosa reputación, que sirve bebidas alcoholicas sin el permiso respectivo. El bar es atendido por tres camareros, que realizan, a petición de los clientes, mezclas de seis bebidas (Whisky, Ginebra, Cognac, Anís del Mono, Cas y Piña).
Los clientes, piden su consumición, que será una combinación cualquiera de dos de las seis bebidas, a un camarero libre, si lo hay. Si todos los camareros están ocupados, esperan a que se libere uno de los tres. El camarero, una vez recibida la petición, coge las botellas correspondientes y hace la mezcla. Mientras tanto, si otro camarero recibe una nueva petición que requiere el uso de una de las botellas que se está utilizando, espera pacientemente a que el otro camarero termine de hacer su mezcla.
Se supone que el máximo número de clientes distintos que se pueden atender en un día está limitado a 100, aunque cada cliente puede pedir tantas combinaciones –gratis- como quiera.
La policía, que sospecha que en el bar se distribuye alcohol sin licencia, puede entrar en cualquier momento en el bar. Cuando así ocurre, los tres camareros sirven a todo el mundo Cas con Piña, independientemente de lo que hayan pedido.
Diseñe un monitor que permita realizar la sincronización de este bar e indique cómo emplearlo para llevarla a cabo.
E) (20 puntos) Un robot explorador tiene un sensor de temperatura y otro de presiónn. Para cada sensor hay un proceso que lee la temperatura y otro que lee la presión. Un tercer proceso realiza determinados cálculos con un par de valores de presión y temperatura. Existen un par de variables donde se almacenan los valores de presión (VP) y temperatura (VP).
Se usen regiones condicionales para sincronizar estos procesos.
El proceso de cálculo sólo ejecute cuando esté disponible un valor de cada tipo.
Los datos sólo se procesan una vez.
Los pares de datos que se procesan están relacionados por el instante de tiempo en que se toman. Si cuando un proceso lector va a proporcionar un dato nuevo al proceso de cálculo detecta que el par anterior no ha sido procesado, deberá anular los valores correspondientes al mismo y escribir el que acaba de leer en la variable adecuada.
F) (15 puntos) Se tiene un sistema con un gran número de procesos que quieren usar un determinado recurso, e interesa que puedan usarlo simultáneamente el máximo número de ellos. Por ejemplo, si 100 procesos quieren usarlo, deben de poder hacerlo los 100 simultáneamente.
Ahora bien, también es necesario impedir (por razones "supersticiosas") que alguna vez estén trece procesos exactamente usando el recurso al mismo tiempo.
Más concretamente, si estando 12 procesos usándolo, un decimotercero desea hacerlo, éste se esperará hasta que llegue un decimocuarto, y entonces entrarán los dos juntos a la región crítica para usar el recurso. Pero en todo caso, si al querer entrar se detecta que existe otro que quiere salir, pero que está esperando para no dejar exactamente 13 dentro, el que entra hará que salga al mismo tiempo que él entra, el que está esperando a salir.
Y simétricamente cuando quiera salir un proceso y haya otro esperando a entrar, así como cuando habiendo uno que quiera salir (sin otro esperando a entrar) quedarían 13 en la región crítica en caso de hacerlo (en este caso se ha de esperar también).
Se pide escribir (con seudocódigo), utilizando semáforos como mecanismo de sincronización, el código que han de ejecutar los procesos tanto al entrar (prólogo) como al salir (epílogo) de esta región crítica especial.
G) (10 puntos) Resuelva el problema del agua empleando los recursos disponibles en Nachos.